11726. Схема Бернулли

Рассмотрим схему испытаний Бернулли.

Проводится n независимых испытаний. Вероятность наступления события А в каждом испытании равна p. Найдите вероятность того, что в n независимых испытаниях случайное событие А произойдет ровно k раз.

Вход. Первая строка содержит два целых числа n (0 < n ≤ 15) и k (0 ≤ k ≤ n).

Вторая строка содержит действительное число p (0 ≤ p ≤ 1).

Выход. Выведите вероятность того, что в n независимых испытаниях случайное событие А произойдет в точности k раз. Ответ следует вывести с точностью не менее 6 десятичных знаков.

Пример входа 1	Пример выхода 1
8 2 0.3	0.296475
Пример входа 2	Пример выхода 2
10 3 0.5	0.117188

РЕШЕНИЕ

теория вероятности

Анализ алгоритма

Испытание Бернулли – это эксперимент с двумя возможными исходами:

· Успех (событие происходит) с вероятностью p,

· Неудача (событие не происходит) с вероятностью 1 – p.

Испытание называется “бернуллиевским”, если оно независимое и вероятность его успеха остаётся постоянной на протяжении всех испытаний.

Схема испытаний Бернулли – это серия независимых испытаний, каждое из которых является испытанием Бернулли. Обозначим количество испытаний через n. В каждом испытании вероятность успеха p и неудачи 1 – p остаются неизменными.

Примером может служить многократное подбрасывание монеты. Если нас интересует, сколько раз выпадет орел из n подбрасываний, то это и будет схема испытаний Бернулли.

Число успехов в серии из n испытаний Бернулли подчиняется биномиальному распределению. Пусть X – случайная величина, которая обозначает число успехов в n испытаниях. Тогда:

P(X = k) =

где

· p – вероятность успеха в каждом испытании,

· k – количество успехов из n испытаний.

Для вычисления значения биномиального коэффициента в действительных числах воспользуемся следующим приемом:

,

Известно, что ln n! = ln (1 * 2 * … * n) = ln 1 + ln 2 + … + ln n

Значения ln i! запоминаем в ячейках массива lf[i]. Далее вычисляем

res = ln n! – ln k! – ln (n – k)! = lf[n] – lf[k] – lf[n – k],

после чего

Пример

В первом тесте проводится n = 8 испытаний. Вероятность наступления события А в каждом испытании равна p = 0.3. Мы хотим найти вероятность того, что событие А произойдет ровно k = 2 раза. Искомая вероятность равна:

P(X = 2) = ≈ 0.296475

Реализация алгоритма

Объявим рабочий массив lf, где lf[i] = ln i! = ln 1 + ln 2 + … + ln i.

#define MAX 1001

double lf[MAX];

Читаем входные данные.

scanf("%d %d", &n, &k);

scanf("%lf", &p);

q = 1 - p;

Заполняем массив lf.

lf[1] = 0;

for (i = 2; i <= n; i++)

lf[i] = lf[i - 1] + log(i);

Вычисляем значение биномиального коеффициента res = .

res = lf[n] - lf[k] - lf[n - k];

res = exp(res);

Вычисляем ответ res = .

for (i = 0; i < k; i++)

res = res * p;

for (i = 0; i < n - k; i++)

res = res * q;

Выводим ответ.

printf("%lf\n", res);